package com.itheima.hanoi;

import java.util.Scanner;

/**
 * @Author: Ethan Yankang
 * @Program: Interview
 * @Date: 2024-08-16 14:37
 **/
public class HanoiTower {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

            int n = input.nextInt();// 圆盘数量
            int total = hanoi(n, 'A', 'B', 'C');
            System.out.println("移动" + n + "个圆盘，需要" + total + "次");
    }

    // 汉诺塔递归函数
    public static int hanoi(int n, char from, char auxiliary, char to) {
        // 基本情况：只有一个圆盘
        if (n == 1) {
            System.out.println("将圆盘 " + n + " 从 " + from + " 移动到 " + to);
            return 1;
        } else {
            // 步骤 1: 将 n-1 个圆盘从 A 移动到 B
         int C1= hanoi(n - 1, from, to, auxiliary);

            // 步骤 2: 将第 n 个圆盘从 A 移动到 C
            System.out.println("将圆盘 " + n + " 从 " + from + " 移动到 " + to);

            // 步骤 3: 将 n-1 个圆盘从 B 移动到 C
         int C2 = hanoi(n - 1, auxiliary, from, to);
         return C1+C2+1;
        }
    }
}
